#ifndef _DOUBLE_RB_TREE_H_
#define _DOUBLE_RB_TREE_H_
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */


#if defined(__x86_64) && defined(_LP64)
#define _RB_USE_AUGMENTED_PTR
#endif


//#ifndef _RB_TREE_NODE_DEFINITION_
//#define _RB_TREE_NODE_DEFINITION_
typedef struct Double_RB_Tree_Node {
  
    struct Double_RB_Tree_Node *left,*right,*parent;
    double key;
    void* data;
    void *prop;

#ifndef _RB_USE_AUGMENTED_PTR 
    unsigned color;
#endif
} Double_RB_Tree_Node;

static inline void double_rb_tree_node_init(Double_RB_Tree_Node* node)
{
    node->left=NULL;
    node->right=NULL;
    node->parent=NULL;
    node->key=-10000;
    node->data=NULL;
    node->prop=NULL;
#ifndef _RB_USE_AUGMENTED_PTR
    node->color=0;
#endif
}
//#endif


typedef struct Double_RB_Tree_Trav{
    
    struct Double_RB_Tree* tree;
    Double_RB_Tree_Node* it;
    void (*next)(struct Double_RB_Tree_Trav*);
    void (*prev)(struct Double_RB_Tree_Trav*); 
    void* second;
    double first;
    void* prop;
}Double_RB_Tree_Trav;

void double_rb_tree_next(struct Double_RB_Tree_Trav* trav);
void double_rb_tree_prev(struct Double_RB_Tree_Trav *trav);
static inline void double_rb_tree_trav_init(Double_RB_Tree_Trav* irtt)
{
    irtt->tree=NULL;
    irtt->it=NULL;
    irtt->next=double_rb_tree_next;
    irtt->prev=double_rb_tree_prev;
    irtt->second=NULL;
    irtt->first=-1000;
    irtt->prop=NULL;
}
typedef struct Double_RB_Tree {
    struct Double_RB_Tree_Node *root;
    void* (*find)(struct Double_RB_Tree*,double);
    void (*insert)(struct Double_RB_Tree*,double key,void* data);
    int (*erase)(struct Double_RB_Tree*,double key);

    struct Double_RB_Tree_Trav (*begin)(struct Double_RB_Tree*);
    struct Double_RB_Tree_Trav (*rbegin)(struct Double_RB_Tree*);

    struct Double_RB_Tree_Node *rightmost; 
    unsigned int size;
    void* prop;
}Double_RB_Tree;
struct Double_RB_Tree* double_rb_tree_copy(struct Double_RB_Tree*);
void double_rb_tree_insert(struct Double_RB_Tree *tree,double key,void* data);
void double_rb_tree_delete_node(struct Double_RB_Tree*tree,struct Double_RB_Tree_Node* node);
int double_rb_tree_delete_key(struct Double_RB_Tree *tree,double key);
Double_RB_Tree_Node* Double_RB_Tree_find(struct Double_RB_Tree *tree,double key);
void* double_rb_tree_findn(struct Double_RB_Tree * tree,double key);
struct Double_RB_Tree_Trav double_rb_tree_begin(Double_RB_Tree*);
struct Double_RB_Tree_Trav double_rb_tree_rbegin(Double_RB_Tree*);

static inline void Double_RB_Tree_init(Double_RB_Tree* irt)
{
    irt->root=NULL;
    irt->find=double_rb_tree_findn;
    irt->insert=double_rb_tree_insert;
    irt->erase=double_rb_tree_delete_key;
    irt->begin=double_rb_tree_begin;
    irt->rbegin=double_rb_tree_rbegin;
    irt->rightmost=NULL;
    irt->size=0;
    irt->prop=NULL;
}
void double_rb_tree_free(struct Double_RB_Tree *tree);
void double_rb_Tree_free_value(struct Double_RB_Tree* tree);









#ifdef __cplusplus
} // extern "C"
#endif /* __cplusplus */


#endif